#include "CFG.h"
#include "LibIO.h"

using namespace CoreLib::IO;

namespace Compiler
{
	namespace Intermediate
	{

		void ControlFlowGraph::AddEdge(ControlFlowNode * node1, int outId, ControlFlowNode * node2)
		{
			node1->Exits[outId] = node2;
			node2->Entries.Add(node1);
		}
		ControlFlowGraph* ControlFlowGraph::FromCode(const Function & func)
		{
			ControlFlowGraph *result = new ControlFlowGraph();
			ControlFlowGraph &rs = *result;
			result->Source = result->AddNode();
			
			List<int> splits;
			rs.Variables.SetSize(func.Parameters.Count() + func.Variables.Count());
			for (int i = 0; i<func.Parameters.Count(); i++)
				rs.Variables[func.Parameters[i]->Id] = func.Parameters[i];
			rs.ParameterCount = func.Parameters.Count();
			for (int i = 0; i<func.Variables.Count(); i++)
				rs.Variables[func.Variables[i]->Id] = func.Variables[i];
#ifdef _DEBUG
			for (int i = 0; i<rs.Variables.Count(); i++)
				if (rs.Variables[i] == 0)
					throw InvalidProgramException(L"Variable ids inconsistent.");
#endif
			auto code = func.Instructions.ToList();
			for (int i = 0; i<code.Count(); i++)
			{
				if (code[i].Func == Operation::Branch || code[i].Func == Operation::Jump)
				{
					if (code[i].Func == Operation::Branch)
						splits.Add(code[i].Operands[1].IntValue);
					else
						splits.Add(code[i].Operands[0].IntValue);
					splits.Add(i + 1);
				}
			}
			splits.Add(code.Count());
			splits.Sort();
			List<int> nSplit;
			nSplit.Reserve(splits.Count());
			if (splits[0] != 0)
				nSplit.Add(0);
			for (int i = 0; i<splits.Count(); i++)
				if (i == 0 || splits[i] != splits[i-1])
					nSplit.Add(splits[i]);
			int ptr = 0;
			int start = 0;
			auto node = rs.AddNode();
			while (ptr<nSplit.Count())
			{
				if (nSplit[ptr] == start)
					ptr++;
				int end = nSplit[ptr];
				for (int i = start; i<end; i++)
				{
					code[i].CFG_Node = node;
					node->Code.AddLast(code[i]);
				}
				start = end;
				if (start < code.Count())
					node = rs.AddNode();
				else
					break;
			}
			for (int i = 0; i<rs.Nodes.Count(); i++)
			{
				auto node = rs.Nodes[i].Ptr();
				if (node->Code.Count() > 0)
				{
					if (node->Code.Last().Func == Operation::Jump)
					{
						int id = nSplit.BinarySearch(node->Code.Last().Operands[0].IntValue) + 1;
						if (id == -1)
							throw InvalidProgramException("Invalid code.");
						AddEdge(node, 0, rs.Nodes[id].Ptr());
						node->Exits[1] = 0;
					}
					else if (node->Code.Last().Func == Operation::Branch)
					{
						int id = nSplit.BinarySearch(node->Code.Last().Operands[1].IntValue)+ 1;
						if (id == -1)
							throw InvalidProgramException("Invalid code.");
						AddEdge(node, 0, rs.Nodes[id].Ptr());
						if (i+1 < rs.Nodes.Count())
						{
							AddEdge(node, 1, rs.Nodes[i+1].Ptr());
						}
					}
					else if (i+1 < rs.Nodes.Count() && node->Code.Count() > 0 && node->Code.Last().Func != Operation::Ret )
					{
						AddEdge(node, 0, rs.Nodes[i+1].Ptr());
					}
				}
			}
			for (int i = 0; i<rs.Nodes.Count(); i++)
			{
				if (rs.Nodes[i]->Code.Count()==0 ||
					rs.Nodes[i]->Code.Last().Func != Operation::Jump &&
					rs.Nodes[i]->Code.Last().Func != Operation::Branch &&
					rs.Nodes[i]->Code.Last().Func != Operation::Ret)
					rs.Nodes[i]->Code.AddLast(Instruction(Operation::Jump, Operand(1)));
			}
			AddEdge(rs.Source, 0, rs.Nodes[1].Ptr());
			result->Sink = result->AddNode();
			AddEdge(rs.Nodes[rs.Nodes.Count()-2].Ptr(), 0, result->Sink);
			rs.ComputeDominatorTree();
			rs.ComputeVariableLiveness();
			return result;
		}

		void ControlFlowGraph::ToCode(Function & func)
		{
			func.Instructions.Clear();
			auto traverse = GetPostOrder();
			Dictionary<int, int> lineMap;
			func.VariableSize = VariableSize;
			for (int i = traverse.Count()-1; i>=0; i--)
			{
				auto node = traverse[i];
				lineMap[node->Id] = func.Instructions.Count();
				for (auto & instr : node->Code)
				{
					auto instrNode = func.Instructions.AddLast(instr);
					if (instr.Func == Operation::Branch)
					{
						instrNode->Value.Operands[1].IntValue = node->Exits[0]->Id;
						func.Instructions.AddLast(Instruction(Operation::Jump, node->Exits[1]->Id));
					}
					else if (instr.Func == Operation::Jump)
					{
						instrNode->Value.Operands[0].IntValue = node->Exits[0]->Id;
					}
				}
			}
			int instrId = 0;
			List<int> removedInstrs;
			for (auto instrNode = func.Instructions.begin(); instrNode != func.Instructions.end(); ++instrNode)
			{
				auto & instr = instrNode.Current->Value;
				if (instr.Func == Operation::Jump)
				{
					int line = lineMap[instr.Operands[0].IntValue];
					if (line == instrId + 1)
					{
						instrNode.Current->Delete();
						removedInstrs.Add(instrId);
					}
					else
						instr.Operands[0].IntValue = line;
				}
				else if (instr.Func == Operation::Branch)
				{
					int line = lineMap[instr.Operands[1].IntValue];
					if (line == instrId + 1)
					{
						instrNode.Current->Delete();
						removedInstrs.Add(instrId);
					}
					else
						instr.Operands[1].IntValue = line;
				}
				instrId++;
			}
			for (auto instrNode = func.Instructions.begin(); instrNode != func.Instructions.end(); ++instrNode)
			{
				auto & instr = instrNode.Current->Value;
				int * line = 0;
				if (instr.Func == Operation::Jump)
				{
					line = &instr.Operands[0].IntValue;
				}
				else if (instr.Func == Operation::Branch)
				{
					line = &instr.Operands[1].IntValue;
				}
				if (line)
				{
					int off = 0;
					for (off = 0; off < removedInstrs.Count(); off++)
						if (removedInstrs[off] > *line)
							break;
					*line -= off;
				}
				instrId++;
			}
			func.Variables.Clear();
			func.Parameters.Clear();
			for (int i = 0; i<Variables.Count(); i++)
				if (i < ParameterCount)
					func.Parameters.Add(Variables[i]);
				else
					func.Variables.Add(Variables[i]);
		}

		void ControlFlowGraph::ComputeDominatorTree()
		{
			// clear
			for (auto & node : Nodes)
			{
				node->DomChildren.Clear();
				node->DominateFrontier.Clear();
				node->ReverseDomChildren.Clear();
				node->ReverseDominateFrontier.Clear();
				node->ImmediateDominator = 0;
				node->ReverseImmediateDominator = 0;
			}
			BuildDominatorTree();
			ComputeDominateFrontier();
			BuildReverseDominatorTree();
			ComputeReverseDominateFrontier();
		}
		void TraverseGraphPostOrder(ControlFlowNode*curNode, List<ControlFlowNode*> &nodes, IntSet & visited)
		{
			if (!visited.Contains(curNode->Id))
			{
				visited.Add(curNode->Id);
				if (curNode->Exits[0])
					TraverseGraphPostOrder(curNode->Exits[0], nodes, visited);
				if (curNode->Exits[1])
					TraverseGraphPostOrder(curNode->Exits[1], nodes, visited);
				nodes.Add(curNode);
			}
		}

		void TraverseReverseGraphPostOrder(ControlFlowNode*curNode, List<ControlFlowNode*> &nodes, IntSet & visited)
		{
			if (!visited.Contains(curNode->Id))
			{
				visited.Add(curNode->Id);
				for (int i = 0; i<curNode->Entries.Count(); i++)
					TraverseReverseGraphPostOrder(curNode->Entries[i], nodes, visited);
				nodes.Add(curNode);
			}
		}

		List<ControlFlowNode *> ControlFlowGraph::GetPostOrder()
		{
			IntSet visited(Nodes.Count());
			List<ControlFlowNode *> rs;
			if (Nodes.Count() != 0)
				TraverseGraphPostOrder(Nodes[0].Ptr(), rs, visited);
			return rs;
		}

		List<ControlFlowNode *> ControlFlowGraph::GetPostOrderOnReverseCFG()
		{
			IntSet visited(Nodes.Count());
			List<ControlFlowNode *> rs;
			if (Nodes.Count() != 0)
				TraverseReverseGraphPostOrder(Nodes.Last().Ptr(), rs, visited);
			return rs;
		}

		template <typename T>
		class FakedList
		{
		public:
			int _count;
			T * _buffer;
			FakedList(int count, T* buffer)
			{
				this->_count = count;
				this->_buffer = buffer;
			}
			int Count()
			{
				return _count;
			}
			T & operator [](int idx)
			{
				return _buffer[idx];
			}
		};

		class ForwardGraphVisitor
		{
		public:
			ControlFlowNode * IntersectDominatorSet(ControlFlowNode * n1, ControlFlowNode * n2, const List<int> & order)
			{
				ControlFlowNode * ptr1, *ptr2;
				ptr1 = n1;
				ptr2 = n2;
				while (ptr1 != ptr2)
				{
					while (order[ptr1->Id] < order[ptr2->Id])
					{
						ptr1 = ptr1->ImmediateDominator;
					}
					while (order[ptr1->Id] > order[ptr2->Id])
					{
						ptr2 = ptr2->ImmediateDominator;
					}
				}
				return ptr1;
			}
			inline ControlFlowNode * GetIDom(ControlFlowNode * node)
			{
				return node->ImmediateDominator;
			}
			inline void SetIDom(ControlFlowNode * node, ControlFlowNode * idom)
			{
				node->ImmediateDominator = idom;
			}
			inline void AddDomChild(ControlFlowNode * node, ControlFlowNode * child)
			{
				node->DomChildren.Add(child);
			}
			inline ControlFlowNode * GetStartNode(ControlFlowGraph & g)
			{
				return g.Nodes.First().Ptr();
			}
			inline List<ControlFlowNode *> GetPostOrder(ControlFlowGraph & g)
			{
				return g.GetPostOrder();
			}
			inline FakedList<ControlFlowNode *> GetEntries(ControlFlowNode * node)
			{
				return FakedList<ControlFlowNode*>(node->Entries.Count(), node->Entries.Buffer());
			}
			inline void AddDomFrontier(ControlFlowNode * node, ControlFlowNode * frontier)
			{
				node->DominateFrontier.Add(frontier);
			}
		};

		class ReverseGraphVisitor
		{
		public:
			ControlFlowNode * IntersectDominatorSet(ControlFlowNode * n1, ControlFlowNode * n2, const List<int> & order)
			{
				ControlFlowNode * ptr1, *ptr2;
				ptr1 = n1;
				ptr2 = n2;
				while (ptr1 != ptr2)
				{
					while (order[ptr1->Id] < order[ptr2->Id])
					{
						ptr1 = ptr1->ReverseImmediateDominator;
					}
					while (order[ptr1->Id] > order[ptr2->Id])
					{
						ptr2 = ptr2->ReverseImmediateDominator;
					}
				}
				return ptr1;
			}
			inline ControlFlowNode * GetIDom(ControlFlowNode * node)
			{
				return node->ReverseImmediateDominator;
			}
			inline void SetIDom(ControlFlowNode * node, ControlFlowNode * idom)
			{
				node->ReverseImmediateDominator = idom;
			}
			inline void AddDomChild(ControlFlowNode * node, ControlFlowNode * child)
			{
				node->ReverseDomChildren.Add(child);
			}
			inline ControlFlowNode * GetStartNode(ControlFlowGraph & g)
			{
				return g.Nodes.Last().Ptr();
			}
			inline List<ControlFlowNode *> GetPostOrder(ControlFlowGraph & g)
			{
				return g.GetPostOrderOnReverseCFG();
			}
			inline FakedList<ControlFlowNode *> GetEntries(ControlFlowNode * node)
			{
				int count = 0;
				if (node->Exits[0] != 0)
					count++;
				if (node->Exits[1] != 0)
					count++;
				return FakedList<ControlFlowNode*>(count, node->Exits);
			}
			inline void AddDomFrontier(ControlFlowNode * node, ControlFlowNode * frontier)
			{
				node->ReverseDominateFrontier.Add(frontier);
			}
		};

		template <typename GraphVisitor>
		void BuildDominateTree_Internal(ControlFlowGraph & graph, GraphVisitor visitor)
		{
			if (graph.Nodes.Count() == 0)
				return;
			IntSet processed(graph.Nodes.Count());
			List<ControlFlowNode*> traverse = visitor.GetPostOrder(graph);
			List<int> order;
			order.SetSize(graph.Nodes.Count());
			for (int i = 0; i<traverse.Count(); i++)
				order[traverse[i]->Id] = i;
			auto startNode = visitor.GetStartNode(graph);
			processed.Add(startNode->Id);
			visitor.SetIDom(startNode, startNode);
			bool changed = true;
			while (changed)
			{
				changed = false;
				for (int i = traverse.Count()-1; i>=0; i--)
				{
					auto curNode = traverse[i];
					if (curNode == startNode) continue;
					ControlFlowNode * newIdom;
					int firstProceedPrecedant = -1;
					auto entries = visitor.GetEntries(curNode);
					for (int j = 0; j<entries.Count(); j++)
					{
						if (processed.Contains(entries[j]->Id))
						{
							newIdom = entries[j];
							firstProceedPrecedant = j;
							break;
						}
					}
					for (int j = 0; j<entries.Count(); j++)
					{
						if (j == firstProceedPrecedant)
							continue;
						if (visitor.GetIDom(entries[j]))
							newIdom = visitor.IntersectDominatorSet(newIdom, entries[j], order);
					}
					if (visitor.GetIDom(curNode)!= newIdom)
					{
						visitor.SetIDom(curNode, newIdom);
						changed = true;
					}
					processed.Add(curNode->Id);
				}
			}
			visitor.SetIDom(startNode, 0);
			for (int i = 0; i<graph.Nodes.Count(); i++)
				if (visitor.GetIDom(graph.Nodes[i].Ptr()))
					visitor.AddDomChild(visitor.GetIDom(graph.Nodes[i].Ptr()), graph.Nodes[i].Ptr());
		}

		template <typename GraphVisitor>
		void ComputeDominateFrontier_Internal(ControlFlowGraph & graph, GraphVisitor visitor)
		{
			for (int i = 0; i<graph.Nodes.Count(); i++)
			{
				auto curNode = graph.Nodes[i].Ptr();
				auto entries = visitor.GetEntries(curNode);
				if (entries.Count() > 1)
				{
					for (int j = 0; j<entries.Count(); j++)
					{
						auto p = entries[j];
						while (p && p != visitor.GetIDom(curNode))
						{
							visitor.AddDomFrontier(p, curNode);
							p = visitor.GetIDom(p);
						}
					}
				}
			}
		}

		void ControlFlowGraph::BuildDominatorTree()
		{
			BuildDominateTree_Internal(*this, ForwardGraphVisitor());
		}

		void ControlFlowGraph::ComputeDominateFrontier()
		{
			ComputeDominateFrontier_Internal(*this, ForwardGraphVisitor());
		}

		void ControlFlowGraph::BuildReverseDominatorTree()
		{
			BuildDominateTree_Internal(*this, ReverseGraphVisitor());
		}

		void ControlFlowGraph::ComputeReverseDominateFrontier()
		{
			ComputeDominateFrontier_Internal(*this, ReverseGraphVisitor());
		}

		void ControlFlowGraph::ComputeVariableLiveness()
		{
			int totalVars = Variables.Count();
			List<IntSet> liveIn, kill;
			liveIn.SetSize(Nodes.Count());
			kill.SetSize(Nodes.Count());
			// compute initial set
			for (int i = 0; i<Nodes.Count(); i++)
			{
				Nodes[i]->LiveOut.SetMax(totalVars);
				Nodes[i]->LiveIn.SetMax(totalVars);
				liveIn[i].SetMax(totalVars);
				kill[i].SetMax(totalVars);
				auto & code = Nodes[i]->Code;
				code.ForEach([&](const Instruction & instr)
				{
					for (int k = 0; k<instr.Operands.Count(); k++)
					{
						if (instr.Operands[k].Type == OperandType::Variable
							&& !kill[i].Contains(instr.Operands[k].Var->Id))
							liveIn[i].Add(instr.Operands[k].Var->Id);
					}
					if (instr.LeftOperand.Type == OperandType::Variable)
						kill[i].Add(instr.LeftOperand.Var->Id);
				});
			}
			if (Nodes.Count()>0)
				Nodes[0]->LiveIn = liveIn[0];
			// iterative solve, in reversed post-order of reserve cfg
			// LiveOut(node) = Union { node.Succeeds sNode, LiveIn(sNode)+(LiveOut(sNode)-Kill(sNode)) }
			auto traverse = GetPostOrderOnReverseCFG();
			bool changed = true;
			IntSet newLiveOut(totalVars);//, partialLiveOut(totalVars);

			while (changed)
			{
				changed = false;
				for (int i = traverse.Count()-1; i>=0; i--)
				{
					newLiveOut.Clear();
					auto node = traverse[i];
					for (int j = 0; j<2; j++)
					{
						if (node->Exits[j] == 0)
							break;
						IntSet & childLiveIn = node->Exits[j]->LiveIn;
						childLiveIn.Clear();
						IntSet::Subtract(childLiveIn, node->Exits[j]->LiveOut, kill[node->Exits[j]->Id]);
						childLiveIn.UnionWith(liveIn[node->Exits[j]->Id]);
						newLiveOut.UnionWith(childLiveIn);
					}
					if (node->LiveOut != newLiveOut)
					{
						node->LiveOut = newLiveOut;
						changed = true;
					}
				}
			}
		}

		void SSA_PlacePhiFunctions(List<RefPtr<ControlFlowNode>> & Nodes, List<RefPtr<Variable>> & Variables)
		{
			List<IntSet> phiSet, lastPhiSet;
			
			lastPhiSet.SetSize(Nodes.Count());
			bool changed = true;
			while (changed)
			{
				changed = false;
				phiSet.SetSize(Nodes.Count());
				for (int i = 0; i<phiSet.Count(); i++)
					phiSet[i].SetMax(Variables.Count());
				for (int i = 0; i<Nodes.Count(); i++)
				{
					IntSet contribution(Variables.Count());
					for (auto & instr : Nodes[i]->Code)
						if (instr.LeftOperand.IsVariable())
							contribution.Add(instr.LeftOperand.Var->Id);
					contribution.IntersectWith(Nodes[i]->LiveOut);
					for (int j = 0; j<Nodes[i]->DominateFrontier.Count(); j++)
					{
						phiSet[Nodes[i]->DominateFrontier[j]->Id].UnionWith(contribution);
					}
					
				}
				for (int i = 0; i<Nodes.Count(); i++)
				{
					phiSet[i].IntersectWith(Nodes[i]->LiveIn);
				}
				for (auto & node : Nodes)
				{
					if (node->Entries.Count() <= 1)
						continue;
					auto & set = phiSet[node->Id];
					for (int j = 0; j<Variables.Count(); j++)
					{
						if (set.Contains(j) && !lastPhiSet[node->Id].Contains(j))
						{
							List<Operand> operands;
							operands.SetSize(node->Entries.Count());
							for (int k = 0; k<node->Entries.Count(); k++)
								operands[k] = Operand(Variables[j].Ptr());
							auto instrNode = node->Code.AddFirst(Instruction(Operand(Variables[j].Ptr()), Operation::Phi, _Move(operands)));
							instrNode->Value.CFG_Node = node.Ptr();
							changed = true;
						}
					}
				}
				if (changed)
					for (int i = 0; i<Nodes.Count(); i++)
					{
						lastPhiSet[i] = _Move(phiSet[i]);
					}
			}
		}

		struct SSA_RootVar
		{
			Variable * Var; // original variable
			List<Variable * > VariableStack; // renamed variable stack for this var
			int Counter;
			SSA_RootVar()
			{
				Var = 0;
				Counter = 0;
			}
		};

		inline Variable * SSA_NewName(Variable * var, ControlFlowGraph * graph, List<SSA_RootVar*> & rootVarMapping)
		{
			Variable * nvar = new Variable();
			nvar->Id = graph->Variables.Count();
			graph->Variables.Add(nvar);
			nvar->Name = var->Name;
			nvar->Size = var->Size;
			auto rootVar = rootVarMapping[var->Id];
			nvar->Version = rootVar->Counter;
			rootVar->Counter++;
			rootVar->VariableStack.Add(nvar);
			rootVarMapping.Add(rootVar);
			return nvar;
		}

		inline void SSA_ReplaceVar(Variable*& var, List<SSA_RootVar*> & rootVarMapping)
		{
			var = rootVarMapping[var->Id]->VariableStack.Last();
		}

		void SSA_Rename(ControlFlowNode * node, ControlFlowGraph * graph, List<SSA_RootVar*> & rootVarMapping)
		{
			// rename instructions
			for (auto iter = node->Code.begin(); iter != node->Code.end(); iter++)
			{
				auto & instr = iter.Current->Value;
				if (instr.Func != Operation::Phi)
				{
					for (auto &op : instr.Operands)
					{
						if (op.IsVariable())
						{
							SSA_ReplaceVar(op.Var, rootVarMapping);
						}
					}
				}
				if (instr.LeftOperand.IsVariable())
				{
					instr.LeftOperand.Var = SSA_NewName(instr.LeftOperand.Var, graph, rootVarMapping);
					graph->VarDefs.Add(iter.Current);
				}
			}
			// update phi functions for child vertices
			for (auto &childNode : node->Exits)
			{
				if (!childNode)
					break;
				int entryId = childNode->Entries.IndexOf(node);
				if (entryId == -1)
					throw InvalidProgramException(L"Inconsistent control flow graph.");
				for (auto & instr : childNode->Code)
				{
					if (instr.Func != Operation::Phi)
					{
						break;
					}
					SSA_ReplaceVar(instr.Operands[entryId].Var, rootVarMapping);
				}
			}
			// recursively process dominate children
			for (auto domChild : node->DomChildren)
				SSA_Rename(domChild, graph, rootVarMapping);
			// restore variable stack
			for (auto &instr : node->Code)
			{
				if (instr.LeftOperand.IsVariable())
				{
					auto & stack = rootVarMapping[instr.LeftOperand.Var->Id]->VariableStack;
					stack.RemoveAt(stack.Count()-1);
				}
			}
		}

		void ControlFlowGraph::ConvertToSSA()
		{
			SSA_PlacePhiFunctions(Nodes, Variables);
			if (Nodes.Count() > 0)
			{
				// intialize mapping between variable aliases and original variables
				List<SSA_RootVar> rootVars;
				rootVars.SetSize(Variables.Count());
				for (int i = 0; i<Variables.Count(); i++)
				{
					rootVars[i].Var = Variables[i].Ptr();
					rootVars[i].VariableStack.Add(Variables[i].Ptr());
					VarDefs.Add(0);
				}
				List<SSA_RootVar*> rootVarMapping;
				rootVarMapping.Reserve(Variables.Count()*2);
				for (int i = 0; i<Variables.Count(); i++)
					rootVarMapping.Add(&rootVars[i]);
				// intialize VarDef
				SSA_Rename(Nodes[0].Ptr(), this, rootVarMapping);
			}
		}

		void ControlFlowGraph::Dump(const String & fileName)
		{
			BinaryWriter writer(new FileStream(fileName, FileMode::Create));
			StringBuilder sb;
			writer.Write(Nodes.Count());
			for (int i = 0; i<Nodes.Count(); i++)
			{
				writer.Write(Nodes[i]->Id);
				sb.Clear();
				for (auto& instr : Nodes[i]->Code)
				{
					sb.Append(instr.ToString());
					sb.Append(L'\n');
				}
				writer.Write(sb.ToString());
				for (int j = 0; j<2; j++)
				{
					if (Nodes[i]->Exits[j])
						writer.Write(Nodes[i]->Exits[j]->Id);
					else
						writer.Write(-1);
				}
				if (Nodes[i]->ImmediateDominator)
					writer.Write(Nodes[i]->ImmediateDominator->Id);
				else
				{
					writer.Write(-1);
				}
				writer.Write(Nodes[i]->DominateFrontier.Count());
				for (int j = 0; j<Nodes[i]->DominateFrontier.Count(); j++)
					writer.Write(Nodes[i]->DominateFrontier[j]->Id);
				writer.Write(Nodes[i]->DomChildren.Count());
				for (int j = 0; j<Nodes[i]->DomChildren.Count(); j++)
					writer.Write(Nodes[i]->DomChildren[j]->Id);
				if (Nodes[i]->ReverseImmediateDominator)
					writer.Write(Nodes[i]->ReverseImmediateDominator->Id);
				else
				{
					writer.Write(-1);
				}
				writer.Write(Nodes[i]->ReverseDominateFrontier.Count());
				for (int j = 0; j<Nodes[i]->ReverseDominateFrontier.Count(); j++)
					writer.Write(Nodes[i]->ReverseDominateFrontier[j]->Id);
			}
		}
	}
}